Online Experiments Practical Lessons.

Seven pitfalls to avoid when running controlled experiments on the web.

Controlled experiments on the web survey and practical guide.
Knowledge Discovery and Data Mining techniques are now commonly used to find novel, potentially useful, patterns in data (Fayyad, et al., 1996; Chapman, et al., 2000). Most KDD applications involve post-hoc analysis of data and are therefore mostly limited to the identification of correlations. Recent seminal work on Quasi-Experimental Designs (Jensen, et al., 2008) attempts to identify causal relationships. Controlled experiments are a standard technique used in multiple fields. Through randomization and proper design, experiments allow establishing causality scientifically, which is why they are the gold standard in drug tests. In software development, multiple techniques are used to define product requirements; controlled experiments provide a way to assess the impact of new features on customer behavior. The Data Mining Case Studies workshop calls for describing completed implementations related to data mining. Over the last three years, we built an experimentation platform system (ExP) at Microsoft, capable of running and analyzing controlled experiments on web sites and services. The goal is to accelerate innovation through trustworthy experimentation and to enable a more scientific approach to planning and prioritization of features and designs (Foley, 2008). Along the way, we ran many experiments on over a dozen Microsoft properties and had to tackle both technical and cultural challenges. We previously surveyed the literature on controlled experiments and shared technical challenges (Kohavi, et al., 2009). This paper focuses on problems not commonly addressed in technical papers: cultural challenges, lessons, and the ROI of running controlled experiments.
Practical guide to controlled experiments on the web listen to your customers not to the hippo.

Online Experiments Lessons Learned.

Focus the Mining Beacon Lessons and Challenges from the World of E%2DCommerce.

Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Visualizing RFM Segmentation.

Lessons and Challenges from Mining Retail E%2DCommerce Data.
Abstract. The architecture of Blue Martini Software’s e-commerce suite has supported data collection, transformation, and data mining since its inception. With clickstreams being collected at the application-server layer, high-level events being logged, and data automatically transformed into a data warehouse using meta-data, common problems plaguing data mining using weblogs (e.g. sessionization and conflating multi-sourced data) were obviated, thus allowing us to concentrate on actual data mining goals. We briefly review the architecture and discuss many lessons learned over the last four years and the challenges still facing us. The lessons and challenges are presented across two dimensions: business-level vs. technical, and throughout the data mining lifecycle stages of data collection, data warehouse construction, business intelligence, and deployment. The lessons and challenges are more widely applicable to data mining domains outside retail e-commerce. Keywords: Data mining, data analysis, business intelligence, web analytics, web mining, OLAP,
WEBKDD 2001 %2D Mining Web Log Data Across All Customers Touch Points
 
Emerging trends in business analytics.
this paper we discuss the technology and enterprise-adoption trends in the area of business analytics. The key consumer of these analytics is the business user, a person whose job is not directly related to analytics per-se (e.g., a merchandiser, marketer, salesperson), but who typically must use analytical tools to improve the results of a business process along one or more dimensions (e.g., profit, time to market). Fortunately, data mining   , analytic applications, and business intelligence systems are now being better integrated with transactional systems creating a closed loop between operations and analyses that allows data to be analyzed faster and the analysis results to be quickly reflected in business actions. Mined information is being deployed to a broader business audience, which is taking advantage of business analytics in everyday activities. Analytics are now regularly used in multiple areas, including sales, marketing, supply chain optimization, and fraud detection [4, 5]
Web Mining.

Integrating E%2DCommerce and Data Mining Architecture and Challenges.
We show that the e-commerce domain can provide all the right ingredients for successful data mining. We describe an integrated architecture for supporting this integration. The architecture can dramatically reduce the pre-processing, cleaning, and data understanding effort often documented to take 80% of the time in knowledge discovery projects. We emphasize the  need for data collection at the application server layer (not the web server) in order to support logging of data and metadata that is essential to the discovery process. We describe the data transformation bridges required from the transaction processing  systems and customer event streams (e.g., clickstreams) to the data warehouse. We detail the mining workbench, which needs to provide multiple views of the data through reporting, data  mining algorithms, visualization, and OLAP. We conclude with a set of challenges.
Real world performance of association rule algorithms.
This study compares five well-known association rule algorithms using three real-world datasets and an artificial dataset. The experimental results confirm the performance improvements previously claimed by the authors on the artificial data, but some of these gains do not carry over to the real datasets, indicating overfitting of the algorithms to the IBM artificial dataset. More importantly, we found that the choice of algorithm only matters at support levels that generate more rules than would be useful in practice. For support levels that generate less than 1,000,000 rules, which is much more than humans can handle and is sufficient for prediction purposes where data is loaded into RAM, Apriori finishes processing in less than 10 minutes. On our datasets, we observed super-exponential growth in the number of rules. On one of our datasets, a 0.02% change in the support increased the number of rules from less than a million to over a billion, implying that outside a very narrow range of support values, the choice of algorithm is irrelevant. Categories and Subject Descriptors H.2.8 [Database Management]: Applications -- Data Mining. Keywords Data Mining, Association Rules, Benchmark, Comparisons, Frequent Itemsets, Market Basket Analysis, Affinity Analysis.
Mining e%2Dcommerce data the good%2C the bad%2C and the ugly.
Organizations conducting Electronic Commerce (e-commerce) can greatly benefit from the insight that data mining of transactional and clickstream data provides. Such insight helps not only to improve the electronic channel (e.g., a web site), but it is also a learning vehicle for the bigger organization conducting business at brick-and-mortar stores. The e-commerce site serves as an early alert system for emerging patterns and a laboratory for experimentation. For successful data mining, several ingredients are needed and e-commerce provides all the right ones (the Good). Web server logs, which are commonly used as the source of data for mining e-commerce data, were designed to debug web servers, and the data they provide is insufficient, requiring the use of heuristics to reconstruct events. Moreover, many events are never logged in web server logs, limiting the source of data for mining (the Bad). Many of the problems of dealing with web server log data can be resolved by properly architecting the ecommerce sites to generate data needed for mining. Even with a good architecture, however, there are challenging problems that remain hard to solve (the Ugly). Lessons and metrics based on mining real e-commerce data are presented. Categories and Subject Descriptors H.2.8 [Database Management]: Applications -- Data Mining. I.2.6 [Artificial Intelligence]: Learning. General Terms Measurement, Design, Experimentation, Human Factors. Keywords E-commerce, data mining, application server, web server, web site architecture. 1.
Applications of Data Mining to Electronic Commerce.
a data mining project. Unfortunately, the other 80% contains several substantial hurdles that without heroic eort may block the successful completion of the project.  The following are ve desiderata for success. Seldom are they they all present in one data mining application.  1. Data with rich descriptions. For example, wide customer records with many potentially useful elds allow data mining algorithms to search beyond obvious correlations.  2. A large volume of data. The large model spaces corresponding to rich data demand many training instances to build reliable models.  3. Controlled and reliable data collection. Manual data entry and integration from legacy systems both are notoriously problematic; fully automated collection is considerably better.  4. The ability to evaluate results. Substantial, demonstrable return on investment can be very convincing.  2 RON KOHAVI AND FOSTER PROVOST 5. Ease of integration with existing processes. Even if pilot studi
Mining E%2DCommerce Data The Good%2C the Bad%2C and the Ugly.
Organizations conducting Electronic Commerce (e-commerce) can greatly benefit from the insight that data mining of transactional and clickstream data provides. Such insight helps not only to improve the electronic channel (e.g., a web site), but it is also a learning vehicle for the bigger organization conducting business at brick-and-mortar stores. The e-commerce site serves as an early alert system for emerging patterns and a laboratory for experimentation. For successful data mining, several ingredients are needed and e-commerce provides all the right ones (the Good). Web server logs, which are commonly used as the source of data for mining e-commerce data, were designed to debug web servers, and the data they provide is insufficient, requiring the use of heuristics to reconstruct events. Moreover, many events are never logged in web server logs, limiting the source of data for mining (the Bad). Many of the problems of dealing with web server log data can be resolved by properly architecting the ecommerce sites to generate data needed for mining. Even with a good architecture, however, there are challenging problems that remain hard to solve (the Ugly). Lessons and metrics based on mining real e-commerce data are presented. Categories and Subject Descriptors H.2.8 [Database Management]: Applications -- Data Mining. I.2.6 [Artificial Intelligence]: Learning. General Terms Measurement, Design, Experimentation, Human Factors. Keywords E-commerce, data mining, application server, web server, web site architecture. 1.
Applications of Data Mining to Electronic Commerce.
a data mining project. Unfortunately, the other 80% contains several substantial hurdles that without heroic eort may block the successful completion of the project.  The following are ve desiderata for success. Seldom are they they all present in one data mining application.  1. Data with rich descriptions. For example, wide customer records with many potentially useful elds allow data mining algorithms to search beyond obvious correlations.  2. A large volume of data. The large model spaces corresponding to rich data demand many training instances to build reliable models.  3. Controlled and reliable data collection. Manual data entry and integration from legacy systems both are notoriously problematic; fully automated collection is considerably better.  4. The ability to evaluate results. Substantial, demonstrable return on investment can be very convincing.  2 RON KOHAVI AND FOSTER PROVOST 5. Ease of integration with existing processes. Even if pilot studi
Web mining for e%2Dcommerce %28workshop session %2D title only%29.

Integrating E%2DCommerce and Data Mining Architecture and Challenges
We show that the e-commerce domain can provide all the right ingredients for successful data mining. We describe an integrated architecture for supporting this integration. The architecture can dramatically reduce the pre-processing, cleaning, and data understanding effort often documented to take 80% of the time in knowledge discovery projects. We emphasize the  need for data collection at the application server layer (not the web server) in order to support logging of data and metadata that is essential to the discovery process. We describe the data transformation bridges required from the transaction processing  systems and customer event streams (e.g., clickstreams) to the data warehouse. We detail the mining workbench, which needs to provide multiple views of the data through reporting, data  mining algorithms, visualization, and OLAP. We conclude with a set of challenges.
Applications of Data Mining to Electronic Commerce
a data mining project. Unfortunately, the other 80% contains several substantial hurdles that without heroic eort may block the successful completion of the project.  The following are ve desiderata for success. Seldom are they they all present in one data mining application.  1. Data with rich descriptions. For example, wide customer records with many potentially useful elds allow data mining algorithms to search beyond obvious correlations.  2. A large volume of data. The large model spaces corresponding to rich data demand many training instances to build reliable models.  3. Controlled and reliable data collection. Manual data entry and integration from legacy systems both are notoriously problematic; fully automated collection is considerably better.  4. The ability to evaluate results. Substantial, demonstrable return on investment can be very convincing.  2 RON KOHAVI AND FOSTER PROVOST 5. Ease of integration with existing processes. Even if pilot studi
Integrating Data Mining into Vertical Solutions.

WEBKDD 2000 %2D Web Mining for E%2DCommerce.

KDD%2DCup 2000 Organizers%27 Report Peeling the Onion.
We describe KDD-Cup 2000, the yearly competition in data mining. For the first time the Cup included insight problems in addition to prediction problems, thus posing new challenges in both the knowledge discovery and the evaluation criteria, and highlighting the need to “peel the onion ” and drill deeper into the reasons for the initial patterns found. We chronicle the data generation phase starting from the collection at the site through its conversion to a star schema in a warehouse through data cleansing, data obfuscation for privacy protection, and data aggregation. We describe the information given to the participants, including the questions, site structure, the marketing calendar, and the data schema. Finally, we discuss interesting insights, common mistakes, and lessons learned. Three winners were announced and they describe their own experiences and lessons in the pages following this paper.
An Empirical Comparison of Voting Classification Algorithms Bagging
Methods for voting classification algorithms, such as Bagging and AdaBoost, have been shown to be very successful in improving the accuracy of certain classifiers for artificial and real-world datasets.  We review these algorithms and describe a large empirical study comparing several variants in conjunction with a decision tree inducer (three variants) and a Naive-Bayes inducer.

The purpose of the study is to improve our understanding of why and
  when these algorithms, which use perturbation, reweighting, and
  combination techniques, affect classification error.  We provide a
  bias and variance decomposition of the error to show how different
  methods and variants influence these two terms.  This allowed us to
  determine that Bagging reduced variance of unstable methods, while
  boosting methods (AdaBoost and Arc-x4) reduced both the bias and
  variance of unstable methods but increased the variance for Naive-Bayes,
  which was very stable.  We observed that Arc-x4 behaves differently
  than AdaBoost if reweighting is used instead of resampling,
  indicating a fundamental difference.  Voting variants, some of which
  are introduced in this paper, include: pruning versus no pruning,
  use of probabilistic estimates, weight perturbations (Wagging), and
  backfitting of data.  We found that Bagging improves when
  probabilistic estimates in conjunction with no-pruning are used, as
  well as when the data was backfit.  We measure tree sizes and show
  an interesting positive correlation between the increase in the
  average tree size in AdaBoost trials and its success in reducing the
  error.  We compare the mean-squared error of voting methods to
  non-voting methods and show that the voting methods lead to large
  and significant reductions in the mean-squared errors.  Practical
  problems that arise in implementing boosting algorithms are
  explored, including numerical instabilities and underflows.  We use
  scatterplots that graphically show how AdaBoost reweights instances,
  emphasizing not only &#034;hard&#034; areas but also outliers and noise.

Pruning Decision Trees with Misclassification Costs.
. We describe an experimental study of pruning methods for decision tree classifiers when the goal is minimizing loss rather than error. In addition to two common methods for error minimization, CART&#039;s cost-complexity pruning and C4.5&#039;s error-based pruning, we study the extension of cost-complexity pruning to loss and one pruning variant based on the Laplace correction. We perform an empirical comparison of these methods and evaluate them with respect to loss. We found that applying the Laplace correction to estimate the probability distributions at the leaves was beneficial to all pruning methods. Unlike in error minimization, and somewhat surprisingly, performing no pruning led to results that were on par with other methods in terms of the evaluation criteria. The main advantage of pruning was in the reduction of the decision tree size, sometimes by a factor of ten. While no method dominated others on all datasets, even for the same domain different pruning mechanisms are better for ...
The Case against Accuracy Estimation for Comparing Induction Algorithms.
We analyze critically the use of classification accuracy to compare classifiers on natural data sets, providing a thorough investigation using ROC analysis, standard machine learning algorithms, and standard benchmark data sets. The results raise serious concerns about the use of accuracy for comparing classifiers and drawinto question the conclusions that can be drawn from such studies. In the course of the presentation, we describe and demonstrate what we believe to be the proper use of ROC analysis for comparative studies in machine learning research. We argue that this methodology is preferable both for making practical choices and for drawing scientific conclusions.
Targeting Business Users with Decision Table Classifiers.
Business users and analysts commonly use spreadsheets and 2D plots to analyze and understand their data. On-line Analytical Processing (OLAP) provides these users with added flexibility in pivoting data around di#erent attributes and drilling up and down the multi-dimensional cube of aggregations. Machine learning researchers, however, have concentrated on hypothesis spaces that are foreign to most users: hyperplanes (Perceptrons), neural networks, Bayesian networks, decision trees, nearest neighbors, etc. In this paper we advocate the use of decision table classifiers that are easy for line-of-business users to understand. We describe several variants of algorithms for learning decision tables, compare their performance, and describe a visualization mechanism that we have implemented in MineSet. The performance of decision tables is comparable to other known algorithms, such as C4.5/C5.0, yet the resulting classifiers use fewer attributes and are more comprehensible. Introduction  Abo...
Guest Editors%27 Introduction On Applied Research in Machine Learning.

Option Decision Trees with Majority Votes.
We describe an experimental study of Option  Decision Trees with majority votes. Option  Decision Trees generalize regular decision  trees by allowing option nodes in addition  to decision nodes; such nodes allow for  several possible tests to be conducted instead  of the commonly used single test. Our goal  was to explore when option nodes are most  useful and to control the growth of the trees  so that additional complexity of little utility  is limited. Option Decision Trees can reduce  the error of decision trees on real-world problems  by combining multiple options, with the  motivation similar to that of voting algorithms  that learn multiple models and combine  the predictions. However, unlikevoting  algorithms, an Option Decision Tree provides  a single structured classifier (one decision  tree), which can be interpreted more easily  by humans. Our results show that for the  tested problems, we can achieve significant  reduction in error rates for trees restricted to  two levels of o...
MineSet An Integrated System for Data Mining.
MineSet TM , Silicon Graphics&#039; interactive system for data mining, integrates three powerful technologies: database access, analytical data mining, and data visualization. It supports the knowledge discovery process from data access and preparation through iterative analysis and visualization to deployment. MineSet is based on a client-server architecture that scales to large databases. The database access component provides a rich set of operators that can be used to preprocess and transform the stored data into forms appropriate for visualization and analytical mining. The 3D visualization capabilities allow direct data visualization for exploratory analysis, including tools for displaying high-dimensional data containing geographical and hierarchical information. The analytical mining algorithms help identify potentially interesting models of the data, which can be viewed using visualization tools specialized for the learned models. Third party vendors can interface to the MineSet...
Wrappers for Feature Subset Selection.
In the feature subset selection problem, a learning algorithm is faced with the problem of selecting a relevant subset of features upon which to focus its attention, while ignoring the rest. To achieve the best possible performance with a particular learning algorithm on a particular domain, a feature subset selection method should consider how the algorithm and the training data interact. We explore the relation between optimal feature subset selection and relevance. Our wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain. We study the strengths and weaknesses of the wrapper approach and show improvements over the original design. We compare the wrapper approach to induction without feature subset selection and to Relief, a filter-based approach to feature subset selection. Significant improvement in accuracy on real problems is achieved for the two families of induction algorithms used: decision trees and Naive-Bayes.
Data Mining Using MLC a Machine Learning Library in C  .
Data mining algorithmsincluding machine learning, statistical analysis, and pattern recognition techniques can greatly improve our understanding of data warehouses that are now becoming more widespread. In this paper, we focus on classification algorithms and review the need for multiple classification algorithms. We describe a system called  MLC++ , which was designed to help choose the appropriate classification algorithm for a given dataset by making it easy to compare the utility of different algorithms on a specific dataset of interest. MLC  ++ not only provides a workbench for such comparisons, but also provides a library of C  ++  classes to aid in the development of new algorithms, especially hybrid algorithms and multi-strategy algorithms. Such algorithms are generally hard to code from scratch. We discuss design issues, interfaces to other programs, and visualization of the resulting classifiers. 1 Introduction  Data warehouses containing massive amounts of data have been b...
Lazy Decision Trees.
Lazy learning algorithms, exemplified by nearestneighbor algorithms, do not induce a concise hypothesis from a given training set; the inductive process is delayed until a test instance is given. Algorithms for constructing decision trees, such as C4.5, ID3, and CART create a single &#034;best&#034; decision tree during the training phase, and this tree is then used to classify test instances. The tests at the nodes of the constructed tree are good on average, but there may be better tests for classifying a specific instance. We propose a lazy decision tree algorithm---LazyDT---that conceptually constructs the &#034;best&#034; decision tree for each test instance. In practice, only a path needs to be constructed, and a caching scheme makes the algorithm fast. The algorithm is robust with respect to missing values without resorting to the complicated methods usually seen in induction of decision trees. Experiments on real and artificial problems are presented.  Introduction  Delay is preferable to error. -...
Bias Plus Variance Decomposition for Zero%2DOne Loss Functions.
We present a bias-variance decomposition of expected misclassification rate, the most commonly used loss function in supervised classification learning.  The bias-variance decomposition for quadratic loss functions is well known and serves as an important tool for analyzing learning algorithms, yet no decomposition was offered for the more commonly used zero-one (misclassification) loss functions until the recent work of Kong &amp; Dietterich (1995) and and Breiman (1996). Their decomposition suffers from some major shortcomings though (e.g., potentially negative variance), which our decomposition avoids.  We show that, in practice, the naive frequency-based estimation of the decomposition terms is by itself biased and show how to correct for this bias. We illustrate the decomposition on various algorithms and datasets from the UCI repository.
Data Mining Using MLC   A Machine Learning Library in C  .
Data mining algorithmsincluding machine learning, statistical analysis, and pattern recognition techniques can greatly improve our understanding of data warehouses that are now becoming more widespread. In this paper, we focus on classification algorithms and review the need for multiple classification algorithms. We describe a system called  MLC++ , which was designed to help choose the appropriate classification algorithm for a given dataset by making it easy to compare the utility of different algorithms on a specific dataset of interest. MLC  ++ not only provides a workbench for such comparisons, but also provides a library of C  ++  classes to aid in the development of new algorithms, especially hybrid algorithms and multi-strategy algorithms. Such algorithms are generally hard to code from scratch. We discuss design issues, interfaces to other programs, and visualization of the resulting classifiers. 1 Introduction  Data warehouses containing massive amounts of data have been b...
Error%2DBased and Entropy%2DBased Discretization of Continuous Features.
We present a comparison of error-based and entropybased methods for discretization of continuous features. Our study includes both an extensive empirical comparison as well as an analysis of scenarios where error minimization may be an inappropriate discretization criterion. We present a discretization method based on the C4.5 decision tree algorithm and compare it to an existing entropy-based discretization algorithm, which employs the Minimum Description Length Principle, and a recently proposed error-based technique. We evaluate these discretization methods with respect to C4.5 and Naive-Bayesian classifiers on datasets from the UCI repository and analyze the computational complexity of each method. Our results indicate that the entropy-based MDL heuristic outperforms error minimization on average. We then analyze the shortcomings of error-based approaches in comparison to entropy-based methods. Introduction  Although real-world classification and data mining tasks often involve con...
Scaling Up the Accuracy of Naive%2DBayes Classifiers A Decision%2DTree Hybrid.
Naive-Bayes induction algorithms were previously shown to be surprisingly accurate on many classification tasks even when the conditional independence assumption on which they are based is violated. However, most studies were done on small databases. We show that in some larger databases, the accuracy of Naive-Bayes does not scale up as well as decision trees. We then propose a new algorithm, NBTree, which induces a hybrid of decision-tree classifiers and Naive-Bayes classifiers: the decision-tree nodes contain univariate splits as regular decision-trees, but the leaves contain Naive-Bayesian classifiers. The approach retains the interpretability of Naive-Bayes and decision trees, while resulting in classifiers that frequently outperform both constituents, especially in the larger databases tested.
The Power of Decision Tables.
. We evaluate the power of decision tables as a hypothesis space for supervised learning algorithms. Decision tables are one of the simplest hypothesis spaces possible, and usually they are easy to understand. Experimental results show that on artificial and real-world domains containing only discrete features, IDTM, an algorithm inducing decision tables, can sometimes outperform state-of-the-art algorithms such as C4.5. Surprisingly, performance is quite good on some datasets with continuous features, indicating that many datasets used in machine learning either do not require these features, or that these features have few values. We also describe an incremental method for performing crossvalidation that is applicable to incremental learning algorithms including IDTM. Using incremental cross-validation, it is possible to cross-validate a given dataset and IDTM in time that is linear in the number of instances, the number of features, and the number of label values. The time for incre...
Supervised and Unsupervised Discretization of Continuous Features.
Many supervised machine learning algorithms require a discrete feature space. In this paper, we review previous work on continuous feature discretization, identify defining characteristics of the methods, and conduct an empirical evaluation of several methods. We compare binning, an unsupervised discretization method, to entropy-based and purity-based methods, which are supervised algorithms. We found that the performance of the Naive-Bayes algorithm significantly improved when features were discretized using an entropy-based method. In fact, over the 16 tested datasets, the discretized version of Naive-Bayes slightly outperformed C4.5 on average. We also show that in some cases, the performance of the C4.5 induction algorithm significantly improved if features were discretized in advance; in our experiments, the performance never significantly degraded, an interesting phenomenon considering the fact that C4.5 is capable of locally discretizing features. 
Autmatic Parameter Selection by Minimizing Estimated Error.

Oblivious Decision Trees%2C Graphs%2C and Top%2DDown Pruning.
We describe a supervised learning algorithm, EODG, that uses mutual information to build an oblivious decision tree. The tree is then converted to an Oblivious read-Once Decision Graph (OODG) by merging nodes at the same level of the tree. For domains that are appropriate for both decision trees and OODGs, performance is approximately the same as that of C4.5, but the number of nodes in the OODG is much smaller. The merging phase that converts the oblivious decision tree to an OODG provides a new way of dealing with the replication problem and a new pruning mechanism that works top down starting from the root. The pruning mechanism is well suited for finding symmetries and aids in recovering from splits on irrelevant features that may happen during the tree construction.  1 Introduction  Decision trees provide a hypothesis space for supervised machine learning algorithms that is well suited for many datasets encountered in the real world (Breiman, Friedman, Olshen &amp; Stone 1984, Quinlan...
A Study of Cross%2DValidation and Bootstrap for Accuracy Estimation and Model Selection.
We review accuracy estimation methods and compare the two most common methods: cross-validation and bootstrap. Recent experimental results on artificial data and theoretical results in restricted settings have shown that for selecting a good classifier from a set of classifiers (model selection), ten-fold cross-validation may be better than the more expensive leaveone-out cross-validation. We report on a largescale experiment -- over half a million runs of C4.5 and a Naive-Bayes algorithm -- to estimate the effects of different parameters on these algorithms on real-world datasets. For cross-validation, we vary the number of folds and whether the folds are stratified or not; for bootstrap, we vary the number of bootstrap samples. Our results indicate that for real-word datasets similar to ours, the best method to use for model selection is ten-fold stratified cross validation, even if computation power allows using more folds. 
Bottom%2DUp Induction of Oblivious Read%2DOnce Decision Graphs Strengths and Limitations.

Feature Subset Selection Using the Wrapper Method Overfitting and Dynamic Search Space Topology.
In the wrapper approach to feature subset selection, a  search for an optimal set of features is made using the  induction algorithm as a blackbox. The estimated  future performance of the algorithm is the heuristic  guiding the search. Statistical methods for feature  subset selection including forward selection, backward  elimination, and their stepwise variants can be viewed  as simple hill-climbing techniques in the space of feature  subsets. We utilize best-first searchtofindagood  feature subset and discuss overfitting problems that  may be associated with searching too many feature  subsets. We introduce compound operators that dynamically  change the topology of the search space to  better utilize the information available from the evaluation  of feature subsets. We show that compound  operators unify previous approaches that deal with  relevant and irrelevant features. The improved feature  subset selection yields significant improvements  for real-world datasets when using the ...
Bottom%2DUp Induction of Oblivious Read%2DOnce Decision Graphs Strengths and Limitations.

Bottom%2DUp Induction of Oblivious Read%2DOnce Decision Graphs.
. We investigate the use of oblivious, read-once decision graphs  as structures for representing concepts over discrete domains, and present a bottom-up, hill-climbing algorithm for inferring these structures from labelled instances. The algorithm is robust with respect to irrelevant attributes, and experimental results show that it performs well on problems considered difficult for symbolic induction methods, such as the Monk&#039;s problems and parity. 1 Introduction  Top down induction of decision trees [25, 24, 20] has been one of the principal induction methods for symbolic, supervised learning. The tree structure, which is used for representing the hypothesized target concept, suffers from some wellknown problems, most notably the replication problem and the fragmentation problem [23]. The replication problem forces duplication of subtrees in disjunctive concepts, such as (A  B)  (C  D); the fragmentation problem causes partitioning of the data into fragments, when a high-arity attrib...
Bottom%2DUp Induction of Oblivious Read%2DOnce Decision Graphs.
. We investigate the use of oblivious, read-once decision graphs  as structures for representing concepts over discrete domains, and present a bottom-up, hill-climbing algorithm for inferring these structures from labelled instances. The algorithm is robust with respect to irrelevant attributes, and experimental results show that it performs well on problems considered difficult for symbolic induction methods, such as the Monk&#039;s problems and parity. 1 Introduction  Top down induction of decision trees [25, 24, 20] has been one of the principal induction methods for symbolic, supervised learning. The tree structure, which is used for representing the hypothesized target concept, suffers from some wellknown problems, most notably the replication problem and the fragmentation problem [23]. The replication problem forces duplication of subtrees in disjunctive concepts, such as (A  B)  (C  D); the fragmentation problem causes partitioning of the data into fragments, when a high-arity attrib...
Irrelevant Features and the Subset Selection Problem.
We address the problem of finding a subset of features that allows a supervised induction algorithm to induce small high-accuracy concepts. We examine notions of relevance and irrelevance, and show that the definitions used in the machine learning literature do not adequately partition the features into useful categories of relevance. We present definitions for irrelevance and for two degrees of relevance. These definitions improve our understanding of the behavior of previous subset selection algorithms, and help define the subset of features that should be sought. The features selected should depend not only on the features and the target concept, but also on the induction algorithm. We describe a method for feature subset selection using cross-validation that is applicable to any induction algorithm, and discuss experiments conducted with ID3 and C4.5 on artificial and real datasets.
MLC   A Machine Learning Library in C  .
We present MLC++, a library of C++ classes and tools for supervised Machine Learning. While MLC++ provides general learning algorithms that can be used by end users, the main objective is to provide researchers and experts with a wide variety of tools that can accelerate algorithm development, increase software reliability, provide comparison tools, and display information visually. More than just a collection of existing algorithms, MLC++ is an attempt to extract commonalities of algorithms and decompose them for a unified view that is simple, coherent, and extensible. In this paper we discuss the problems MLC++ aims to solve, the design of MLC++, and the current functionality.  
Research Note on Decision Lists.

